from typing import List


class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        # 左边最大 小于等于 右边最小
        inf = float('inf')
        n = len(nums)
        left = [inf] * n
        right = [inf] * n
        left[0] = nums[0]
        right[n-1] = nums[n-1]
        for i in range(1,n):
            left[i] = max(left[i-1],nums[i])
        for i in range(n-2,-1,-1):
            right[i] = min(right[i+1], nums[i])
        ans = 0
        for i in range(n):
            if i + 1 < n and left[i] <= right[i+1]:
                return i + 1


if __name__ == "__main__":
    s = Solution()
    r = s.partitionDisjoint([1,1,1,0,6,12])
    print(r)